/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
	vector<string> split(string s){
		istringstream iss(s);
		string cache;
		vector<string> res;
		while(getline(iss, cache, ',')){
			res.push_back(cache);
		}
		return res;
	}

	int getHeight(struct TreeNode* node){
		if(node){
			return max(getHeight(node->left), getHeight(node->right)) + 1;
		}
		return 0;
	}

    // Encodes a tree to a single string.
    string serialize(struct TreeNode* root) {
		if(root == nullptr){
			return "";
		}
        int height = getHeight(root);
		string res;
		
		serializeMid(root, height, res);
		return res;
    }
	
	void serializeMid(struct TreeNode * head, int height, string & res){
		if(head != nullptr || height > 0){
			height--;
			if(head != nullptr){
				serializeMid(head->left, height, res);
				res += to_string(head->val) + ",";
			}else{
				serializeMid(nullptr, height, res);
				res += "null,";
			}
			
			if(head != nullptr){
				serializeMid(head->right, height, res);
			}else{
				serializeMid(nullptr, height, res);
			}
		}else{
			return;
		}
	}

	void show(struct TreeNode * head){
		if(head){
			show(head->left);
			cout << head->val << ",";
			show(head->right);
		}
	}
    // Decodes your encoded data to tree.
    struct TreeNode* deserialize(string data) {
		if(data == ""){
			return nullptr;
		}
		vector<string> dataV = split(data);
        int len = dataV.size();
		int mid = len/2;
		struct TreeNode * head = new TreeNode(stoi(dataV[mid]));
		if(len > 1){
			combine(head, {dataV.begin(), dataV.begin() + mid}, {dataV.begin() + mid + 1, dataV.end()});
		}
		
		return head;
    }
	
	void combine(struct TreeNode * head, vector<string> leftV, vector<string> rightV){
		int len = leftV.size();
		int mid = len/2;
		struct TreeNode * leftNode;
		struct TreeNode * rightNode;
		
		if(leftV[mid] != "null"){
			leftNode = new TreeNode(stoi(leftV[mid]));
			head->left = leftNode;
		}
		if(rightV[mid] != "null"){
			rightNode = new TreeNode(stoi(rightV[mid]));
			head->right = rightNode;
		}
		
		if(len == 1){
			return;
		}
		
		if(leftV[mid] != "null"){
			combine(leftNode,{leftV.begin(), leftV.begin() + mid},{leftV.begin() + mid + 1, leftV.end()});
		}
		if(rightV[mid] != "null"){
			combine(rightNode,{rightV.begin(), rightV.begin() + mid},{rightV.begin() + mid + 1, rightV.end()});
		}
		
	}
	
	struct TreeNode * init(){
		// struct TreeNode * head = new TreeNode(0);
		struct TreeNode * head = new TreeNode(0);
		// struct TreeNode * n1 = new TreeNode(1);
		// struct TreeNode * n1 = new TreeNode(1);
		// head->left = n1;
		
		// struct TreeNode * n2 = new TreeNode(2);
		// struct TreeNode * n2 = new TreeNode(2);
		// head->right = n2;
		
		// struct TreeNode * n3 = new TreeNode;
		// n3->val = 3;
		// n3->left = nullptr;
		// n3->right = nullptr;
		// n1->left = n3;
		
		// struct TreeNode * n4 = new TreeNode;
		// n4->val = 4;
		// n4->left = nullptr;
		// n4->right = nullptr;
		// n1->right = n4;
		
		// struct TreeNode * n5 = new TreeNode(5);
		// n2->left = n5;
		
		// struct TreeNode * n6 = new TreeNode(6);
		// n2->right = n6;
		
		// struct TreeNode * n7 = new TreeNode;
		// n7->val = 7;
		// n7->left = nullptr;
		// n7->right = nullptr;
		// n3->left = n7;
		
		// struct TreeNode * n8 = new TreeNode;
		// n8->val = 8;
		// n8->left = nullptr;
		// n8->right = nullptr;
		// n3->right = n8;
		
		// struct TreeNode * n9 = new TreeNode;
		// n9->val = 9;
		// n9->left = nullptr;
		// n9->right = nullptr;
		// n4->left = n9;
		
		// struct TreeNode * n10 = new TreeNode;
		// n10->val = 10;
		// n10->left = nullptr;
		// n10->right = nullptr;
		// n4->right = n10;
		
		// struct TreeNode * n11 = new TreeNode(11);
		// n5->left = n11;
		
		// struct TreeNode * n12 = new TreeNode(12);
		// n5->right = n12;
		
		// struct TreeNode * n13 = new TreeNode(13);
		// n6->left = n13;
		
		// struct TreeNode * n14 = new TreeNode(14);
		// n6->right = n14;
		
		return head;
	}
	
};

int main(){
	Codec code;
	struct TreeNode * node = code.init();
	code.show(node);
	cout << endl;

	string res = code.serialize(node);
	
	struct TreeNode * newNode = code.deserialize(res);
	code.show(newNode);
	// cout << res << endl;
	return 0;
}




// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;